1. Field of the Invention
This invented system and method are related to use of fractal-transform based descriptors as compact descriptors of an image. The system and method can also use the descriptors to search a database for target images similar to a source image.
2. Description of the Related Art
One fundamental problem in image management is the classification of imagery according to the presence or absence of particular features or textures. This problem is most notable in defense and medical applications when the presence of particular objects or artifacts can be the signal for further tests, increased monitoring, or other actions. While all images of a critical nature must be evaluated by an expert, a fast, reliable pre-screening methodology can contribute to the overall process by bringing those images that are most likely to contain an important object or artifact to the attention of the analyst. A related problem in image management is to describe entire images in terms of a small number of parameters with the goals of facilitating database retrieval and enabling a xe2x80x9cquery by contentxe2x80x9d mode for image data. The first problem can be viewed as a special case of the second: one can break the high resolution image into sub-images, possibly overlapping, and query a database consisting of descriptors of the subimages with descriptors of images consisting of the sought after objects, textures or artifacts. Pixel-to-pixel comparisons are not suitable for solving these problems, and several types of image descriptors and description schemes have been proposed for the solution over the last decade. These methods include the xe2x80x9cSloanxe2x80x9d and xe2x80x9cMarie-Juliexe2x80x9d methods that use fractal transform (FT) codes to generate descriptors for an image.
In fractal image compression, an image of pixels is broken into equally-sized groups of pixels referred to as xe2x80x98domain blocksxe2x80x99. Larger groups of pixels referred to as xe2x80x98range blocksxe2x80x99 are positioned adjacent or in near proximity to a particular domain block and are reduced to a size comparable to the domain block. The pixel intensities of the domain block are compared with those of the range blocks to determine a range block that is closest in intensity distribution to the domain block. The process is repeated domain-block-by-domain-block to determine range blocks closest in pixel intensity to respective domain blocks of the pixel image. This process allows intensity patterns that repeat within the image to be found and used to compress the image into a more compact, less data-intensive form. This is advantageous, for example, in transmitting images over communication media with limited bit rates. On the receiving end of the communication media, the compacted pixel image can be decompressed to obtain the original pixel image. The image can thus be transmitted in much less time than would otherwise be required.
The comparison of range and domain blocks yields error vectors indicative of the pixel-by-pixel error between the domain blocks and respective range blocks yielding the smallest error. Until the development of this invention, the error vector has been discarded after use in determining the range block closest to a particular domain block to compress an image. It would be desirable if some beneficial use could be found for this error vector which is a necessary by-product of many image compression processes.
A first method in accordance with the invention can be used with image data divided into domain blocks. A predetermined search pattern of range blocks centered on a domain block is defined for use in the method. The first method includes a step of generating at least one type of error descriptor data, based on domain block data and range block data. The error descriptor data can be derived by scaling the range blocks to the pixel size of a domain block and subtracting means of range blocks and domain block from the respective pixels thereof. The pixel intensity levels of the domain block are subtracted from the scaled, mean-adjusted pixel intensity levels of the range blocks to produce difference data. The absolute value of the difference data is taken and the difference data are summed to produce summed error data. The summed error data is used to derive at least one error descriptor data. The error descriptor data is a relatively compressed representation of the image data. The error descriptor data can include collage error descriptor data, address histogram error descriptor data, flatness error descriptor data, soft decision error descriptor data, collage error distribution descriptor data, and/or range error descriptor data.
A second method of the invention includes culling target error descriptor data for target images stored in a database, based on error descriptor data for a source image and at least one predetermined threshold level. The second method can also include scoring the culled target error descriptor data, and ranking the target error descriptor data by score to determine the relative closeness of the target images to the source image.
A system of the invention includes a processor generating error descriptor data for at least one image based on domain block data and range block data. The system can also include at least one memory coupled to the processor, for storing the domain block data, range block data, and error descriptor data. The memory can be used to store a database of error descriptor data for target images. The processor can be programmed to compare error descriptor data for the target images with the error descriptor data for the source image to cull and score error descriptor data of the target images to determine target images relatively similar to the source image. The system can further include an input device coupled to the processor, for generating a signal under manipulation by the user to select or indicate an image to be converted by the processor into error descriptor data. The system can further include a scanner coupled to the processor, for scanning an image to generate image data supplied to the processor. The processor can generate error descriptor data based on the scanned image data. In addition, the system can include a display unit coupled to the processor. The processor can generate display data based on the error descriptor data. The processor can be coupled to supply the display data supplied to the display unit to generate a visual display of at least one of the source and target images.
These together with other objects and advantages, which will become subsequently apparent, reside in the details of construction and operation as more fully hereinafter described and claimed, reference being made to the accompanying drawings, forming a part hereof, wherein like numerals refer to like parts through the several views.